'''
https://leetcode.cn/problems/trim-a-binary-search-tree/
'''
from typing import Optional

from c06_tree.utils import TreeNode


class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:

        def process(root):
            if not root: return None
            if low <= root.val <= high:
                # 在范围之间
                root.left = process(root.left)
                root.right = process(root.right)
            elif root.val < low:
                # 小于左边界了，去我的右子树看看
                root = process(root.right)
            else:
                # 大于右边界了，去我的左子树看看
                root = process(root.left)
            return root

        return process(root)
